__author__ = 'st316'
'''
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
'''


class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        flag1r = False
        flag1c = False
        if 0 in matrix[0]:
            flag1r = True
        for i in xrange(len(matrix)):
            if matrix[i][0] == 0:
                flag1c = True
                break
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[i])):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0
        for i in xrange(1, len(matrix)):
            for j in xrange(1, len(matrix[i])):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if flag1r:
            matrix[0] = [0 for x in xrange(len(matrix[0]))]
        if flag1c:
            for i in xrange(len(matrix)):
                matrix[i][0] = 0


if __name__ == '__main__':
    s = Solution()
    m = [[1, 0]]
    s.setZeroes(m)
    print m